#!/usr/bin/env python
# encoding: utf-8
"""
MS_GSP.py
Implement of MS_GSP algorithm in Python

BY:
Peng Yang, Xiaoxiao Xu, Yuzong Liu @ WUSTL

Usage:

Python MS_GSP.py [options] 

See Python MS_GSP.py -h (--help) for details

options: 
    -d(--data) dataFileName 
    -p(--para) parameterFileName 
    -o(--o) outputFileName

Copyright (c) 2011 . All rights reserved.
"""

import sys, os
import re
import string
import util
import copy
from dataSequence import *

from optparse import OptionParser

# Command options
parser  = OptionParser(version="%prog 1.0",\
                       usage="python %prog [options]")

parser.add_option("-d", "--data", action="store",\
        type="string", dest="dataFile",\
        default='data-2.txt',\
        help="data file name[default='data.txt']")

parser.add_option("-p", "--para", action="store",\
        type="string", dest="paraFile",\
        default="para2-1.txt",\
        help="parameter file name [default='para.txt']")

parser.add_option("-o", "--out", action="store",\
        type="string", dest="OUT",\
        default="MSGSPResult.txt",\
        help="output file name [default=MSGSPResult.txt]")

(options, args) = parser.parse_args()


MIS = {}    # MIS Value
SDC = 0.0    # Support DifferenceConstraint
SequenceDataset = []    # Sequence Dataset
SplitLine =  "***************************\n"


" Data Initilization "
MIS, SDC = util.readMISFile(options.paraFile, MIS, SDC)
#MIS, SDC = util.readMISFile("paraTest.txt", MIS, SDC)
print "MIS = " + str(MIS)
print "SDC = " + str(SDC)
#SequenceDataset = util.readDataFile('dataTest.txt',SequenceDataset)
SequenceDataset = util.readDataFile(options.dataFile,SequenceDataset)
print "SequenceDataset = " + str(SequenceDataset)
M = util.sort(MIS)
print "M = " + str(M)
n = len(SequenceDataset)


def init_pass(M,S,MIS):
    # M = sorted index of the item according to MIS
    # S = all sequences from the transaction data file
    # return L, which is the seed for generating candidates of length 2
#    print "MS-GSP starting initial pass ..."
#    print SplitLine
    n = len(S)
    L = {}
    for item in M:
        L[item] = 0
    minMIS = MIS[M[0]]
    # print minMIS
    "first scans the data to record support count"
    for sequence in S:
        for item in M:
            # if an element appear more than once in one sequence, we only count once
            L[item]=L[item]+(util.isItemInElement(item,sequence) > 0)
    "find first element satisfies the min MIS"        
    ipInd = 0
#    for item in M:
#        if float(L[item])/n < MIS[item]:
#            del L[item]
#            ipInd += 1
#        else:
#            ipMIS = MIS[item]
#            break
#    for index in range(ipInd,len(M)):
#        if float(L[M[index]]) < ipMIS:
#            del L[M[index]]
#        else:
#            continue    
        
    for ipInd in range(0, len(M)):
        if float(L[M[ipInd]])/n < MIS[M[ipInd]]:
            del L[M[ipInd]]
            ipInd +=1
        else:
            ipMIS = MIS[M[ipInd]]
            break
    for index in range(ipInd,len(M)):
        if float(L[M[index]])/n < ipMIS:
            del L[M[index]]
        else:
            continue
        
#        else:
#            print SplitLine
#            return L
#    print SplitLine
    print L
    return L        

def generateF1(L):
    print SplitLine
#    print "*\tfreq. 1-itemset\t*"
#    print "#\titem.count/n \tMIS "
    F1 = []
    for key in L:
        if float(L[key])/n < MIS[key]:
            continue
        else:
            # print str(key) + "\t" + str(float(L[key])/n) + "\t" + str(MIS[key])
            F1.append(dataSequence([[key]],L[key],MIS[key],key))
    return F1        

def level2_candidate_gen(L,SDC):
#    print SplitLine    
#    print "generating level-2 candidate ...\n"
    C2 = []
    allItems = L.keys()
#    print "allItems= "+ str(allItems)
    
    for i in range(0,len(M)):
        if not M[i] in allItems:
            continue
#        if float(L[M[i]])/n >= MIS[M[i]]:
        for j in range(0,len(M)):
#                if M[j]==M[i]:
#                    continue
            if not M[j] in allItems:
                continue
#                if float(L[M[j]])/n >= MIS[M[i]] and abs(MIS[M[i]]-MIS[M[j]]) <= SDC:
            if (float(L[M[i]])/n >= min(MIS[M[i]], MIS[M[j]]) and float(L[M[j]])/n >= min(MIS[M[i]], MIS[M[j]]) ) and abs(float(L[M[i]])/n-float(L[M[j]])/n) <= SDC:
                if M[i] < M[j]:
                    C2.append(dataSequence([[M[i],M[j]]]))
                C2.append(dataSequence([[M[i]],[M[j]]]))
    return C2    

def print_level2_candidate(C2):
    print "itemset" + "\t\t" + "count" + "\t" + "minSup" + "\t" + "minItem"
    for item in C2:
        print str(item.itemset) + "\t\t" + str(item.count) + '\t' + str(item.minSup) +'\t' + str(item.minItem)
        
def print_freqSequence(F,k):
    print SplitLine
    print "*      freq. "+str(k)+"-itemset    *"
    print SplitLine
    print 'itemset' + ':' + 'count'
    for item in F[k]:
        print str(item.itemset) + ":" + str(item.count)
                    
            
def MScandidate_gen_SPM(oldF):
    C = []
    for i in range(0,len(oldF)):
        for j in range(0, len(oldF)):
            s1 = copy.deepcopy(oldF[i].itemset)
            s2 = copy.deepcopy(oldF[j].itemset)
            tmp1 = util.getAllItems(s1)
            V1 = []
            for item in tmp1:
                V1.append(MIS[item])
            tmp2 = util.getAllItems(s2)
            V2 = []
            for item in tmp2:
                V2.append(MIS[item])
            "Case 1: if MIS(s1 1st item) < MIS(s1 others)"
#            print "Case 1"
            if V1[0] <= min(V1[1:len(V1)]):      
#                print "Case 1"
                "s1-2nd == s2-last && MIS(s2 last) > MIS(s1 first)"
                s1_dropsecond = copy.deepcopy(s1)
                s2_droplast = copy.deepcopy(s2)
                if len(s1[0]) == 1:             # remove second item from s1
                    s1_dropsecond[1].remove(s1_dropsecond[1][0])
                else:
                    s1_dropsecond[0].remove(s1_dropsecond[0][1])
                if len(s2[len(s2)-1]) == 1:     # remove last item from s2
                    s2_droplast = s2[0:len(s2)-1]
                else:
                    s2_droplast[len(s2_droplast)-1].remove(s2_droplast[len(s2_droplast)-1][len(s2_droplast[len(s2_droplast)-1])-1])
                s1_dropsecond=util.reshapeSequence( s1_dropsecond)
                s2_droplast=util.reshapeSequence( s2_droplast)
                flag1 = util.isEqual(s1_dropsecond,s2_droplast)
                flag2 = MIS[s2[-1][-1]] >= MIS[s1[0][0]]
                if flag1 and flag2:
                    if len(s2[-1]) == 1:        # s2 last item is separate
                        s1_tmp = copy.deepcopy(s1)
                        s1.append(s2[-1])
                        C.append(dataSequence(s1))
                        flag3 = (len(s1_tmp) == 2 and util.lenSequence(s1_tmp) == 2)
                        flag4 = float(s2[-1][-1]) > float(s1_tmp[-1][-1]) 
                        if flag3 and flag4:
                            s1_tmp[-1].append(s2[-1][-1])
                            C.append(dataSequence(s1_tmp))
                    elif (len(s1) == 1 and util.lenSequence(s1) == 2 and float(s2[-1][-1]) > float(s1[-1][-1])) or util.lenSequence(s1) > 2:
                        s1[-1].append(s2[-1][-1])
                        C.append(dataSequence(s1))
                continue
            "Case 2: if MIS(s2 last item) < MIS(s2 others)"
#            print "Case 2"
            if V2[-1] <= min(V2[0:len(V2)-1]):  
#                print "Case 2"
                "s1-1st == s2-second last && MIS(s2 last) < MIS(s1 first)"
                s1_dropfirst = copy.deepcopy(s1)
                s2_dropseclast = copy.deepcopy(s2)
                if len(s1[0]) == 1:             # remove first item from s1
                    s1_dropfirst = s1[1:len(s1)]
                else:
                    s1_dropfirst[0].remove(s1_dropfirst[0][0])
                if len(s2[len(s2)-1]) == 1:     # remove second last item from s2
                    s2_dropseclast[len(s2_dropseclast)-2].remove(s2_dropseclast[len(s2_dropseclast)-2][len(s2_dropseclast[len(s2_dropseclast)-2])-1])
                else:
                    s2_dropseclast[len(s2_dropseclast)-1].remove(s2_dropseclast[len(s2_dropseclast)-1][len(s2_dropseclast[len(s2_dropseclast)-1])-2])
                s1_dropfirst=util.reshapeSequence(s1_dropfirst)
                s2_dropseclast=util.reshapeSequence(s2_dropseclast)
                flag1 = util.isEqual(s1_dropfirst,s2_dropseclast)
                flag2 = MIS[s2[-1][-1]] <= MIS[s1[0][0]]
                if flag1 and flag2:
                    if len(s1[0]) == 1:        # s1 first item is separate
                        s2_tmp=copy.deepcopy(s2)
                        s2.insert(0,s1[0])
                        C.append(dataSequence(s2))
                        flag3 = (len(s2_tmp) == 2 and util.lenSequence(s2_tmp) == 2)
                        flag4 = float(s1[0][0]) < float(s2_tmp[0][0]) 
                        if flag3 and flag4:
#                            print s2_tmp
#                            print s1
                            s2_tmp[0].insert(0,s1[0][0])
                            C.append(dataSequence(s2_tmp))
                    elif (len(s2) == 1 and util.lenSequence(s2) == 2 and float(s1[0][0]) < float(s2[0][0])) or util.lenSequence(s2) > 2:
                        s2[0].insert(0,s1[0][0])
                        C.append(dataSequence(s2))
                continue
            "Case 3: other situations, use candidate-gen-SPM(oldF)"
#            print "Case 3"
            s1_dropfirst = copy.deepcopy(s1)
            s2_droplast = copy.deepcopy(s2) 
            if len(s1[0]) == 1:
                s1_dropfirst = s1[1:len(s1)] # remove first item from s1
            else:
                s1_dropfirst[0].remove(s1_dropfirst[0][0]) 
            if len(s2[len(s2)-1]) == 1:    # remove last item from s2
                s2_droplast[0:len(s2_droplast)-1]
            else:
                s2_droplast[len(s2_droplast)-1].remove(s2_droplast[len(s2_droplast)-1][len(s2_droplast[len(s2_droplast)-1])-1])
            s1_dropfirst=util.reshapeSequence(s1_dropfirst)
            s2_droplast=util.reshapeSequence(s2_droplast)
            if util.isEqual(s1_dropfirst,s2_droplast):
                if len(s2[-1]) == 1:    # if the added item is separate
                    s1.append(s2[-1])
                    C.append(dataSequence(s1))
                else:
                    s1[-1].append(s2[-1][-1])
                    C.append(dataSequence(s1))
    "Prune Step"
#    print_level2_candidate(C)
    outputC=[]
    cind = {}
    for seqind in range(0, len(C)):
        cind[seqind] = 1
        sequence = copy.deepcopy(C[seqind].itemset)
        for i in range(0, len(sequence)):
            for j in range(0,len(sequence[i])):
                Tsequence = copy.deepcopy(sequence)
                Tsequence[i].remove(Tsequence[i][j])        # remove one item in sequence
                Tsequence = util.reshapeSequence(Tsequence)
                flag1 = util.isSequenceFrequent(Tsequence, oldF)
                flag2 = util.findMIS(Tsequence, MIS) == util.findMIS(sequence, MIS)
                if (not flag1) and flag2:
                    cind[seqind] = 0
                    break
                else:
                    continue
            if (not flag1) and flag2:
                break
    for i in range(0,len(cind)):
        if cind[i]:
            outputC.append(C[i])
#    print len(outputC)
    return outputC         


# def main():
"MS-GSP Algorithm Starts form Here!!!"
F={}
C={}
L = init_pass(M,SequenceDataset,MIS)
k=1
F[1] = generateF1(L)
k+=1
while len(F[k-1])>0:
    if k==2:
        C[k] = level2_candidate_gen(L,SDC)
    else:
        C[k] = MScandidate_gen_SPM(F[k-1])
    for s in SequenceDataset:
        for c in C[k]:
            items = util.getAllItems(c.itemset)
            for item in items:
                if MIS[item] < c.minSup:
                    c.minSup = MIS[item]
                    c.minItem = item
            if util.isContained(c.itemset,s):
                c.count += 1
    F[k] = []
    for c in C[k]:
        if float(c.count)/n >= MIS[c.minItem]:
            F[k].append(dataSequence(c.itemset,c.count,c.minSup,c.minItem))
    k+=1
"FINAL RESULT"
fo = open(options.OUT,'w')
for i in range(0,len(F)-1):
    fo.write("The number of length "+str(i+1)+" sequential patterns is "+str(len(F[i+1]))+"\n")
    print "The number of length "+str(i+1)+" sequential patterns is "+str(len(F[i+1]))
    for item in F[i+1]:
        fo.write(util.formatStr(item.itemset) + " Count: " + str(item.count) + '\n')
        print util.formatStr(item.itemset) + " Count: " + str(item.count)
    print "\n"
    fo.write("\n")
fo.close()        
    
# if __name__ == '__main__':
#     main()


                